package pers.qianyu.month_202101.date_20210120;

import org.junit.*;
import pers.qianyu.util.*;
import pers.qianyu.util.model.*;

/**
 * 687. 最长同值路径
 * https://leetcode-cn.com/problems/longest-univalue-path/
 *
 * @author mizzle rain
 * @date 2021-01-20 16:37
 */
public class LongestUnivaluePath {
    private int res;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        recur(root);
        return res;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = root.left != null ? 1 + recur(root.left) : 0;
        int right = root.right != null ? 1 + recur(root.right) : 0;
        if (root.left != null && root.left.val != root.val) left = 0;
        if (root.right != null && root.right.val != root.val) right = 0;
        res = Math.max(res, left + right);
        return Math.max(left, right);
    }

    @Test
    public void test1() {
        TreeNode root = BinTreeUtil.generateBinTree(new Integer[]{1, 4, 5, 4, 4, 5});
        int result = new LongestUnivaluePath().longestUnivaluePath(root);
        System.out.println("result = " + result);
        Assert.assertEquals(result, 2);
    }
}
